This invention relates to rings used in a telecommunications network, and more particularly to a process for use in designing such rings which reduces the number of add/drop multiplexers used in the ring.
In recent years, telecommunications network providers have been faced with satisfying user demand for significantly higher network capacity and greater reliability. To handle the capacity demands, long distance carriers are turning to Synchronous Optical Network (xe2x80x9cSONETxe2x80x9d) and Wavelength Division Multiplexing (xe2x80x9cWDMxe2x80x9d) to provide networks with gigabit per second links. To meet the demands for greater reliability, self-healing rings are being deployed to provide restoration times on the order of tens of milliseconds in the event of a cable cut or an office failure. These network upgrades will necessitate billions of dollars of new equipment installation. Ring design techniques that reduce the amount of terminal equipment required in rings, and therefore reduce the cost of deploying rings in a network, are becoming increasingly commercially important.
Designing rings to be deployed in a network is a multi-step process. Typically, the first step is laying out the topology of the rings, which involves selecting the offices (or nodes) that when connected by fiber will make up the various rings. In a national-scale network, there are likely to be tens of rings.
The next step is to route traffic demands between the offices. The input into this process is the traffic demand matrix between each pair of offices, where the granularity of the demands is OC-M, for some Mxe2x89xa71 (OC-1 is the smallest SONET carrier level, representing 50 Mbit/sec; OC-M represents xe2x80x9cMxe2x80x9d times this rate).
Once the path for each OC-M has been laid out, the next step is to group the OC-Ms together to form OC-Ns (for Nxe2x89xa7M), where OC-N is the optical line rate. A commercially important embodiment is a ring in which M equals three (3) and N equals forty-eight (48), although the discussion holds for more general N and M.
In a backbone network, there are typically multiple OC-48s (i.e., multiple OC-48 optical signals) that must be routed on a single ring; such multiplicity of OC-48s is often referred to as xe2x80x98stacked ringsxe2x80x99. Using WDM techniques up to eight OC-48s (or more, depending on the technology) can be multiplexed on a single fiber. When multiple OC-48s are present in a ring, there are numerous ways to group the OC-3s (time slots) to form the OC-48s (optical signals). Such grouping process is commonly referred to as xe2x80x98ring bundlingxe2x80x99.
The choice of techniques used to accomplish the ring design steps enumerated above (i.e., topology design, routing, ring-bundling) can greatly impact the cost of the network. One design approach is to integrate all of the steps into a single optimization problem, where minimizing cost is the objective. However, in a national-scale network, the size and complexity of such an integrated approach would likely make the problem intractable. Alternatively, each of the steps can be considered an independent problem, with heuristics applied to each step.
Topology design strategies are discussed in the article by Wasam, O. J., Wu, T. H., and Cardwell, R. H., entitled xe2x80x9cSurvivable SONET networks-design methodology,xe2x80x9d IEEE Journal on Selected Areas in Communications, vol. 12, no. 1, pp. 205-212, January, 1994; the article by To, M., and McEachern, J., entitled xe2x80x9cPlanning and deploying a SONET-based metro network,xe2x80x9d IEEE LTS, vol. 2, pp. 19-23, November, 1991; and the article by Laguna, M., entitled xe2x80x9cClustering for the design of SONET rings in interoffice telecommunications,xe2x80x9d Management Science, vol. 40, No. 11, pp. 1533-1541, November, 1994. Routing traffic demands between offices of the ring is typically done with variations of shortest-path routing that take into account load balancing.
Conventionally, the OC-48 optical signal is terminated at each office in the ring in an add/drop multiplexer (xe2x80x9cADMxe2x80x9d). The ADM provides a multiplexing function between the OC-48 signal and lower rate signals such as OC-1 or OC-3 signals. The ADM allows these lower rate signals to be dropped and added at the office, while passing (i.e., allowing to pass through) the signals that do not need to be dropped. If no portion of the OC-48 signal needs to be dropped at an office, then it is possible to remove the ADM from the office, and have the OC-48 xe2x80x98expressxe2x80x99 through the office instead of being terminated. ADMs for OC-48 signals cost on the order of hundreds of thousands of dollars. Thus, eliminating ADMs from the ring can result in significant cost savings.
A process for ring bundling according to the invention reduces the number of ADMs required for a ring deployed in a telecommunications network by grouping lower rate signals together that pass through the same office. The input into the process is a list of all the time slots (i.e., channel assignments) for a ring and the offices where each of the time slots adds or drops traffic. Time slots that have many add/drops in common are grouped together according to the process. For example, if the time slots are at the OC-3 signal rate, initially they are grouped in pairs, then in fours, then in eights, and finally in groups of sixteen to form an OC-48 optical signal.
According to an illustrative embodiment of the invention, a xe2x80x98compatibilityxe2x80x99 metric is calculated for each pair of time slots. The pairs are then sorted from most compatible to least compatible. Beginning with the most compatible pair, pairs of time slots are selected to form time-slot pairs, until every time slot is included in one and only one time-slot pair. Next, a compatibility metric is calculated for each pair of time-slot pairs (four time slots). The sets of four time slots are sorted from most compatible to least compatible. Beginning with the most compatible pair of time-slot pairs, pairs of time-slot pairs are selected until every time slot is selected once and only once. Then, time slots are grouped into sets of eight, and finally into groups of sixteen. The add/drops that are present in a group of sixteen time slots represent the offices of the ring where ADMs are required.
Other features and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, which illustrate, by way of example, the features of the invention.